Computer graphics have evolved from the crude data displayed on monitors, printers or hardcopy plotters of early computers to the computationally complex three-dimensional (3D) images of today. Early computers could not show complex computer graphics primarily because hardware was expensive and computer performance was slow. Since then, advances in technology have caused computer graphics hardware prices to drop dramatically and performance of graphics hardware has drastically improved. At the same time, graphics processing techniques have become more sophisticated and efficient. Today, many desktop computers support 3D computer graphics through improved and relatively inexpensive graphics accelerating hardware (accelerators). Video game consoles also include specialized graphics hardware.
A graphics accelerator is a type of video device that contains its own processor to boost performance levels. These processors are specialized for computing graphical transformations, so they achieve better results than the general-purpose processor (i.e., the central processing unit, or CPU) used by the computer. In addition, a graphics accelerator frees up the computer's CPU to execute other commands while the graphics accelerator is handling graphics computations. One basic function of graphics accelerators is displaying graphical primitives (e.g., lines, polygons, curves, and textual characters). Another basic function is putting constraints on primitives, for example, to enforce how graphical objects move in relation to other objects, such as how a revolving door turns around its pillar or how a drawer moves along runners in its cabinet. Other functions include performing algorithms for dragging objects, rubberbanding (i.e., graphically resizing objects), and transforming (e.g. rotating, scaling, or translating) an image. Graphics accelerators typically also process data structures for storing object models such as geometric models.
I. Geometric Models
Geometric modeling is an important area of 3D computer graphics, which deals with the representation and manipulation of graphical objects in a computer. In early stages, computer graphics were two-dimensional (2D). Displayed objects were defined by complicated and lengthy sequences of drawing commands. For performance reasons, it became important to distinguish between the model of the object to be displayed and the display primitives on the screen at a given time for the object. For objects viewed from different perspectives, distances, or contexts, it became more efficient to represent the object with one model from which different images were rendered as necessary, rather than as a collection of different images (with drawing primitives) for various views. To “render” an object means to create an image for display from the object, considering the object itself and potentially other information such as light sources and perspective. The distinction between the object model and display primitives became even more important in 3D computer graphics because of the increased complexity of the objects and increased display detail.
Today, geometric modeling provides a way to model physical and virtual (computer generated) objects on a computer. In their most basic application, geometric models are computational (symbolic) structures that capture the spatial aspects of the objects of interest. In addition to spatial information, many models store information such as color, texture, and so on to accurately represent objects. These geometric models form the foundation of powerful simulation and modeling tools.
For example, through the use of geometric modeling, computers can perform realistic simulations of car crashes in a non-destructive fashion, analyze the stresses in aerospace structures during flight, and perform pre-surgical planning such as simulating the implantation of an artificial limb.
Moreover, 3D computer graphics have become more important in multimedia and Internet applications. For example, movie special effects and video games are increasingly driven by 3D computer graphics. Online retailers can now showcase online object models of sales items to customers, which allow customers to peruse an item before buying it. All of these and other functions use geometric modeling and illustrate its usefulness.
II. Meshed Object Models Overview
The use of polygonal meshes for the representation of highly complex geometric objects has become the generally accepted standard in most computer graphics applications. The reason for this is that flexible and effective processing and storage techniques have been developed which usually work for models and shapes with arbitrary topology.
A mesh is made up of connected points. In one common kind of model, each of the points has three coordinate values (x, y, z), which correspond to width, height, and depth. Some meshes are entirely computer generated. Other meshes are based on measured data points, where the raw data is obtained by mechanical or optical scanning of an object's surface. Adjacent points may be connected to produce triangles, quadrilaterals, or other polygonal shapes. For example, points are converted into a triangle mesh by connecting nearby points into triangles according to some set of rules. Generally, triangle meshes are preferred due to their algorithmic simplicity, numerical robustness, and efficient display. Geometrically, a triangle mesh has a piecewise surface (e.g. a surface composed of sub-regions or sub-divisions) consisting of triangular shapes (or “faces”) joined together along their edges. An advantage of triangle meshes is that they can be used for many stages of the typical processing pipeline in geometric design and graphics applications without the need for data conversion. This decreases the overall processing time and reduces the potential for round-off errors (which are more likely to be introduced with more data conversions).
A regular mesh has uniform patches and a predictable structure and connectivity, which allows for efficient representation and processing in computers. Regularity also enables the use of various signal-processing techniques (e.g., for compression). A drawback of regular meshes is their lack of flexibility in resolving shapes with high genus (an indicator of the number of handles or tunnels on a body bounded by a closed surface) or detail at different levels. In contrast, irregular meshes are more flexible than regular meshes and can better resolve complex geometric features, at the cost of greater complexity in representation and processing.
Once a mesh model exists, it may be analyzed for surface quality (e.g., fidelity to an original surface), representation efficiency, and other criteria. Remeshing modifies the sampling and connectivity of a geometric mesh to generate a new mesh, for example, approximating the first mesh, refining the first mesh, or converting the first mesh to another representation. Remeshing may involve using new or different vertices for a mesh, and also may involve comparing samples from the new mesh to some original highly detailed surface. This process is called resampling.
The number of vertices affects the complexity of a mesh. It also characterizes the computational costs required to display or modify the mesh. Hence, for computationally more expensive operations a mesh with fewer triangles would be preferred. Along that same vein, a high performance computer can handle images and models of greater complexity since they have more computational resources. Other factors such as mesh regularity (discussed below) and mesh shape also may affect computational performance.
III. Regular Remeshing
Regular remeshing is a term describing methods whereby an irregular mesh for an object is approximated by a mesh with regular or semi-regular connectivity. The simplicity of regularly remeshed representation has many benefits. One key benefit is that it eliminates the indirection and storage of vertex indices and texture coordinates. (In a regular mesh, vertices and shape connectivity follow a predictable pattern. Graphics hardware is better able to assess which vertices it will need at any given time and have those loaded in memory.) This allows graphics hardware to perform rendering more efficiently by removing random memory accesses. Thus, memory performance improves.
Of various remeshing techniques, the geometry image (GIM) technique creates the most regular remeshed representation. The GIM technique was introduced by the article X. Gu, S. J. Gortler, and H. Hoppe, Geometry Images, SIGGRAPH 2002, pp. 355-361, 2002 (“Gu”). The construction described in the Gu article converts a surface into a topological disk using a network of cuts, and parameterizes the resulting disk onto a square domain. Using this parameterization, the surface geometry is resampled onto the pixels of an image. This technique has some benefits, including the fact that image compression can be directly applied to the remesh. However, the Gu approach of mapping an entire surface to a single square has limitations. First, models having disconnected components require a separate geometry image for each component. More importantly, complicated shapes with many extremities or topological handles/tunnels have distorted parameterizations due to stretching and squashing of the complicated shapes to flatten and fit them into the image. On rendering, every sample within the geometry image is defined since the model fills the image.
A less extreme approach than regular remeshing is to create a remesh with the connectivity of a subdivided base mesh. Examples of this approach are sometimes called semi-regular remeshing, and include methods described in the articles: (1) M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsberry, and W. Stuetzle, Multiresolution Analysis of Arbitrary Meshes, SIGGRAPH 1995, pp. 173-182, 1995 (“Eck”); (2) A. Lee, H. Moreton, and H. Hoppe, Displaced Subdivision Surfaces, SIGGRAPH 2000, pp. 85-94, 2000 (“Lee 1998”); (3) A. Lee, W. Sweldens, P. Schröder, L. Cowsar, and D. Dobkin, MAPS: Multiresolution Adaptive Parameterization of Surfaces, SIGGRAPH 1998, pp. 95-104, 1998 (“Lee 2000”); (4) L. Kobbelt, J. Vorsatz, U. Labsik, and H. P. Seidel, A Shrink Wrapping Approach to Remeshing Polygonal Surfaces, Eurographics 1999, pp. 119-130, 1999 (“Kobbelt”); (5) I. Guskov, K. Vidimce, W. Sweldens, and P. Schröder, Normal Meshes, SIGGRAPH 2000, pp. 355-361, 2000 (“Guskov”); and (6) Z. J. Wood, M. Desbrun, P. Schröder, and D. Breen, Semi-regular Mesh Extraction from Volumes, IEEE Visualization 2000, pp. 275-282, 2000 (“Wood”). For example, a base version (i.e., a coarse, low-detail version) of a mesh is created and sub-divided into base-level triangles, and additional details for the sub-divided base mesh are provided in additional mesh layers. For these representations, special kinds of continuous multiresolution basis functions can be derived that allow multiresolution editing and compression.
These approaches provide a more flexible representation than pure regular remeshing, yet still have constraints that can negatively impact parameterization efficiency. In particular, each chart (here, a surface region associated with a triangle of the base mesh) is effectively parameterized onto an equilateral triangle, which is then evenly sampled. Charts with non-triangular shapes are distorted by the parameterization. For example, charts that are long and skinny are invariably sampled anisotropically (i.e., not exhibiting uniformity along different axes), and are hence distorted. In addition, these remesh techniques require that all charts, regardless of their size or information content, be allotted the same number of samples.
IV. Atlas Parameterization
Another framework for mesh processing and remeshing is atlas parameterization. Some atlas parameterization schemes map individual triangles or pairs of triangles separately into a texture. For example, such techniques are described in the articles: (1) N. Carr, and J. Hart in Meshed Atlases for Real-time procedural solid texturing, ACM Transactions on Graphics. 21 (2), pp. 106-131, 2002 (“Carr”); and (2) P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno in A General Method for Recovering Attribute Values on Simplified Meshes, IEEE Visualization 1998, pp. 59-66, 1998 (“Cignoni”). Other, more general, chart-based atlas constructions include those described in the articles: (1) J. Maillot, H Yahia, and A. Verroust, Interactive Texture Mapping, SIGGRAPH 1993, pp. 27-34, 1993 (“Maillot”); (2) D. Piponi and G. D. Borshukov, Seamless Texture Mapping of Subdivision Surfaces by Model Pelting and Texture Blending, SIGGRAPH 2000, pp. 471-478, 1993 (“Piponi”); (3) P. V. Sander, J. Snyder, S. J. Gortler, and H. Hoppe, Texture Mapping Progressive Meshes, SIGGRAPH 2001, pp. 409-416, 2001 (“Sander”); (4) B. Lévy, S. Petitjean, N. Ray, and J. Maillot, Least Squares Conformal Maps for Automatic Texture Atlas Generation, SIGGRAPH 2002, pp. 362-371, 2002 (“Lévy”); (5) O. Sorkine, D. Cohen-Or, R. Goldenthal, and D. Lischinski, Bounded-distortion Piecewise Mesh Parameterization, IEEE Visualization 2002, 2002 (“Sorkine”); and (6) A. Sheffer and J. C. Hart, Seamster: Inconspicuous Low-Distortion Texture Seam Layout, IEEE Visualization 2002, 2002 (“Sheffer”).
The Maillot article describes partitioning a mesh into charts based on bucketing face normals. The parameterization method optimizes edge springs of non-zero rest length.
The Piponi article describes manually cutting a subdivision surface using a network of edges. This chart-base atlas construction parameterizes the resulting single chart using a “pelting” analogy, by stretching out the surface boundary using a collection of springs.
The Sander article describes partitioning a mesh using greedy face clustering. The construction parameterizes the resulting charts onto convex polygons using geometric stretch. The charts are packed into a square using a greedy algorithm based on bounding rectangles. Areas between the convex polygons in the square are then filled with valid values.
The Lévy article describes aligning chart boundaries with high-curvature features of the surface. After locating a set of seed faces farthest from sharp features, the technique grows charts about these seeds and merges some of the resulting charts. Additionally, the Lévy article describes parameterizing each chart using least-squares conformal maps with free boundaries and using a Tetris-like packing algorithm that searches for best fit over the horizon of pieces packed so far.
The Sorkine article describes simultaneously growing charts and parameterizing them. The chart growth stops when a distortion limit is reached or if self-overlap is detected. At this point, a new chart is started. The Sorkine parameterization uses a stretch-based metric that penalizes both undersampling and oversampling.
The Sheffer article describes cutting a surface into a single chart by cutting through high-distortion, less-visible surface regions.
A key drawback to these atlas constructions is that none addresses the problem of inter-chart cracks in reconstructions due to resampling geometry images. Reconstructed signals are discontinuous across chart boundaries. Irregular chart outlines do not align with the sampling grid; therefore, boundaries between neighboring charts are generally sampled differently. For geometry images, such signal discontinuities create unacceptable cracks in the surface. In fact, even a few erroneous pixels become glaring artifacts.
Moreover, these atlas construction methods are greedy, thus their trade-off solutions between performance and final product may miss good results.
V. Model Decomposition
Others have investigated model decomposition outside of the context of remeshing. For example, the article S. Shlafman, A. Tal, and S. Katz in Metamorphosis of Polyhedral Surfaces Using Decomposition, Eurographics 2002, pp. 219-228, 2002 (“Shlafman”) describes a clustering-based approach to mesh partitioning. However, the Shlafman approach is used for morphing and not parameterization, therefore, its clustering distance metric does not account for overall chart planarity.
VI. Zippering
Outside of the context of remeshing, others have investigated how to handle the problem of cracks between meshes during reconstruction. For example, the article G. Turk, and M. Levoy in Zippered Polygon Meshes from Range Images, SIGGRAPH 1994, pp. 311-318, 1994 (“Turk”) describes reconstructing watertight surfaces from scanned height meshes by “zippering” mesh boundaries together. In their implementation, the desired surface is unknown, which makes their zippering technique a challenging operation. Therefore, there exists a need for a simple, yet robust zippering technique.
Several others have considered the problem of reconstructing surfaces from contours, for example, in the article H. Fuchs, Z. Kedem, and S. Uselton, Optimal Surface Reconstruction from Planar Contours, Comm. ACM 20, 1977 (“Fuchs”). The simplest case the Fuchs article describes is that of building a surface ribbon that spans two parallel contour polygons. This involves constructing a ribbon of new triangles along the gap between vertices instead of trying to unify the vertices across the gap.
Previous remeshing and chartification techniques do not provide an adequately efficient and simple 2D representation for arbitrary 3D surfaces, including those with extremities and handles/tunnels. Moreover, previous techniques do not address the problem of cracks between meshes during reconstruction. Finally, previous techniques leave much room for improvement for chartification solutions that are both computationally practical and effective.